/*
 * AVLTree.h
 * The implementation of a typical AVL tree.
 *  Created on: 2013-1-16
 *      Author: EthanHuang
 */

#ifndef AVLTREE_H_
#define AVLTREE_H_
#include <iostream>
#include "BasicUtility.h"

template<typename ComparableType> class AVLTree
{
public:
	AVLTree();
	AVLTree(const AVLTree& rhs);
	~AVLTree();

	const ComparableType& findMax() const;
	const ComparableType& findMin() const;
	bool contains(const ComparableType& x) const;
	bool isEmpty() const;
	void printTree() const;

	//Delete all BinaryNode that in the BinarySearchTree
	void makeEmpty();
	void insert(const ComparableType& x);
	void remove(const ComparableType& x);
	//make a clone of a BinarySearchTree
	const AVLTree& operator=(const AVLTree& tree);

private:

	struct AVLNode
	{
		AVLNode(const ComparableType& elm, AVLNode* lt, AVLNode* rt, int h = 0) :
				elm(elm), left(lt), right(rt), height(h)
		{
		}
		~AVLNode()
		{
			left = right = NULL;
		}
		//The actual AVLNode should hold a element that inherit Comparable
		//interface
		ComparableType elm;
		AVLNode *left;
		AVLNode *right;
		int height;
	};

	//Note: the reference to the pointer of a tree node, makes it easy to
	//modify the tree
	AVLNode* _root;

	int height(AVLNode* t) const
	{
		return (NULL == t) ? -1 : t->height;
	}

	void rotateWithRightChild(AVLNode*& tree)
	{
		AVLNode* right = tree->right;
		tree->right = right->left;
		right->left = tree;
		tree->height = BasicUtility::max(height(tree->left), height(tree->right)) + 1;
		right->height = BasicUtility::max(height(right->right), tree->height) + 1;
		tree = right;
	}


	void rotateWithLeftChild(AVLNode*& tree)
	{
		AVLNode* left = tree->left;
		tree->left = left->right;
		left->right = tree;
		tree->height = BasicUtility::max(height(tree->left), height(tree->right)) + 1;
		left->height = BasicUtility::max(height(left->left), tree->height) + 1;
		tree = left;
	}

	void doubleRotateWithLeftChild(AVLNode *&tree)
	{
		rotateWithRightChild(tree->left);
		rotateWithLeftChild(tree);
	}


	void doubleRotateWithRightChild(AVLNode *&tree)
	{
		rotateWithLeftChild(tree->right);
		rotateWithRightChild(tree);
	}

	void _insert(const ComparableType& x, AVLNode* & tree)
	{
		//insert into a null tree
		if(NULL == tree)
		{
			tree = new AVLNode(x, NULL, NULL);
		}
		//insert into the left
		else if(x < tree->elm)
		{
			_insert(x, tree->left);
			if(2 == height(tree->left) - height(tree->right) )
			{
				if(x < tree->left->elm)
					rotateWithLeftChild(tree);
				else
					doubleRotateWithLeftChild(tree);
			}
		}
		//insert into the right
		else if (x > tree->elm)
		{
			_insert(x, tree->right);
			if(2 == height(tree->right) - height(tree->left) )
			{
				if(x > tree->right->elm)
					rotateWithRightChild(tree);
				else
					doubleRotateWithRightChild(tree);
			}
		}
		//duplication, ignore
		else	{}

		//adjust tree->height
		tree->height = BasicUtility::max(height(tree->left), height(tree->right) ) + 1;
	}

	void _remove(const ComparableType& x, AVLNode* & tree) const
	{

	}

	AVLNode* _findMax(AVLNode* t) const
	{
		if(NULL != t)
		{
			while(NULL != t->right)
				t= t->right;
			return t;
		}
	}

	AVLNode* _findMin(AVLNode* x) const
	{
		if(NULL == x)
		{
			return NULL;
		}
		if(NULL == x->left)
		{
			return x;
		}
		return _findMin(x->left);
	}

	bool _contains(const ComparableType& x, AVLNode* t) const
	{
		if(NULL == t)
		{
			return false;
		}
		else if(x > t->elm)
		{
			_contains(x, t->right);
		}
		else if(x < t->elm)
		{
			_contains(x, t->left);
		}
		else
			return true;
	}

	void _makeEmpty(AVLNode* node)
	{
		if( NULL != node)
		{
			_makeEmpty(node->left);
			_makeEmpty(node->right);
			delete node;
		}
		node = NULL;
	}

	void _printTree(AVLNode* node) const
	{
		if(NULL != node)
		{
			std::cout<<node->elm<<" ";
			_printTree(node->left);
			_printTree(node->right);
		}
	}

	AVLNode* clone(AVLNode* node) const
	{
		if(NULL == node)
			return NULL;
		return new AVLNode(node->elm, clone(node->left), clone(node->right), 0);
	}

};

template<typename ComparableType>
inline AVLTree<ComparableType>::AVLTree() :
		_root(NULL)
{
}

template<typename ComparableType>
inline AVLTree<ComparableType>::AVLTree(
		const AVLTree& rhs)
{
	_root = clone(rhs._root);
}

template<typename ComparableType>
inline AVLTree<ComparableType>::~AVLTree()
{
	makeEmpty();
}

template<typename ComparableType>
inline const ComparableType& AVLTree<ComparableType>::findMax() const
{
	return _findMax(_root)->elm;
}

template<typename ComparableType>
inline const ComparableType& AVLTree<ComparableType>::findMin() const
{
	return _findMin(_root)->elm;
}

template<typename ComparableType>
inline bool AVLTree<ComparableType>::contains(
		const ComparableType& x) const
{
	return _contains(x, _root);
}

template<typename ComparableType>
inline bool AVLTree<ComparableType>::isEmpty() const
{
	return this->_root = NULL ? true : false;
}

template<typename ComparableType>
inline void AVLTree<ComparableType>::printTree() const
{
	std::cout<<"The AVL tree is :"<<std::endl;
	_printTree(_root);
}

template<typename ComparableType>
inline void AVLTree<ComparableType>::makeEmpty()
{
	_makeEmpty(_root);
}

template<typename ComparableType>
inline void AVLTree<ComparableType>::insert(const ComparableType& x)
{
	_insert(x, _root);
}

template<typename ComparableType>
inline void AVLTree<ComparableType>::remove(const ComparableType& x)
{
	_remove(x, _root);
}

template<typename ComparableType>
inline const AVLTree<ComparableType>& AVLTree<ComparableType>::operator =(
		const AVLTree<ComparableType>& tree)
{
	if(tree != this)
	{
		makeEmpty();
		_root = clone(tree._root);
	}
	return *this;
}

#endif /* AVLTREE_H_ */
